#include <iostream>
#include <climits>
using namespace std;
void merge(int* arr, int p, int q, int r){
int n1=q-p+1;
int n2=r-q;
int L[n1+1], R[n2+1];
int i, j;
for(i=0; i<n1; ++i){
L[i]=arr[p+i];
}
for(j=0; j<n2; ++j){
R[j]=arr[q+j+1];
}
L[n1]=INT_MAX; R[n2]=INT_MAX;
i=0; j=0;
for(int k=p; k<=r; ++k){
if(L[i]<=R[j]){
arr[k]=L[i];
i++;
} else {
arr[k]=R[j];
j++;
}
}
}
void merge_sort(int* arr, int p, int r){
if(p<r){
int q=(p+r)/2;
merge_sort(arr, p, q);
merge_sort(arr, q+1, r);
merge(arr, p, q, r);
}
}
int main(void){
int arr[]={5, 2, 4, 6, 1, 3};
int size=sizeof(arr)/sizeof(int);
merge_sort(arr, 0, 5);
for(int i=0; i<size-1; ++i){
cout<<arr[i]<<", ";
}
cout<<arr[size-1]<<endl;
}